class SortingSearchingAlgorithm:
    @staticmethod
    def merge_sorted_arrays(nums1, m, nums2, n):
        """
        合并两个有序数组算法

        参数:
        nums1 (List[int]): 第一个有序数组
        m (int): 第一个数组中实际元素的个数
        nums2 (List[int]): 第二个有序数组
        n (int): 第二个数组中元素的个数

        实现步骤:
        1. 创建一个辅助数组，用于存储合并后的有序数组
        2. 使用双指针分别指向两个数组的末尾元素
        3. 从后向前遍历辅助数组，比较两个指针指向的元素大小，并将较大的元素放入辅助数组中
        4. 如果第二个数组还有剩余元素，将剩余元素依次放入辅助数组的前面
        5. 将辅助数组的元素复制到第一个数组中

        """

        # 步骤 1: 创建一个辅助数组
        merged = [0] * (m + n)

        # 步骤 2: 使用双指针
        p1 = m - 1
        p2 = n - 1

        # 步骤 3: 从后向前遍历辅助数组
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] >= nums2[p2]:
                merged[p1 + p2 + 1] = nums1[p1]
                p1 -= 1
            else:
                merged[p1 + p2 + 1] = nums2[p2]
                p2 -= 1

        # 步骤 4: 处理剩余元素
        if p2 >= 0:
            merged[:p2 + 1] = nums2[:p2 + 1]

        # 步骤 5: 复制到第一个数组
        nums1[:m + n] = merged

    @staticmethod
    def rotate_array(nums, k):
        """
        旋转数组算法

        参数:
        nums (List[int]): 输入的数组
        k (int): 旋转的步数

        实现步骤:
        1. 对k进行取模，处理大于数组长度的情况
        2. 将整个数组反转
        3. 反转前k个元素
        4. 反转后n-k个元素

        """

        # 步骤 1: 对k进行取模
        k = k % len(nums)

        # 步骤 2: 反转整个数组
        nums.reverse()

        # 步骤 3: 反转前k个元素
        nums[:k] = reversed(nums[:k])

        # 步骤 4: 反转后n-k个元素
        nums[k:] = reversed(nums[k:])

    @staticmethod
    def search_rotated_sorted_array(nums, target):
        """
        搜索旋转排序数组算法

        参数:
        nums (List[int]): 输入的旋转排序数组
        target (int): 目标值

        返回:
        int: 目标值在数组中的索引，如果不存在则返回-1

        实现步骤:
        1. 使用二分搜索，定义左右边界
        2. 在每次迭代中，根据中间值判断旋转点在左半部分还是右半部分
        3. 根据旋转点的位置判断目标值在哪个半部分，缩小搜索范围
        4. 在缩小后的范围内使用普通的二分搜索找到目标值

        """

        # 步骤 1: 定义左右边界
        left = 0
        right = len(nums) - 1

        # 步骤 2: 二分搜索
        while left <= right:
            mid = (left + right) // 2

            # 步骤 3: 判断旋转点在左半部分还是右半部分
            if nums[mid] == target:
                return mid
            elif nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        # 步骤 4: 普通二分搜索
        return -1

if __name__ == '__main__':
    # 示例调用合并两个有序数组算法
    nums1 = [1, 2, 3, 0, 0, 0]
    m = 3
    nums2 = [2, 5, 6]
    n = 3
    SortingSearchingAlgorithm.merge_sorted_arrays(nums1, m, nums2, n)
    print("合并两个有序数组算法:")
    print("输入:", nums1, m, nums2, n)
    print("输出:", nums1)
    """
    示例输出结果:
    输入: [1, 2, 3, 0, 0, 0] 3 [2, 5, 6] 3
    输出: [1, 2, 2, 3, 5, 6]
    """

    # 示例调用旋转数组算法
    nums = [1, 2, 3, 4, 5, 6, 7]
    k = 3
    SortingSearchingAlgorithm.rotate_array(nums, k)
    print("旋转数组算法:")
    print("输入:", nums, k)
    print("输出:", nums)
    """
    示例输出结果:
    输入: [1, 2, 3, 4, 5, 6, 7] 3
    输出: [5, 6, 7, 1, 2, 3, 4]
    """

    # 示例调用搜索旋转排序数组算法
    nums = [4, 5, 6, 7, 0, 1, 2]
    target = 0
    search_result = SortingSearchingAlgorithm.search_rotated_sorted_array(nums, target)
    print("搜索旋转排序数组算法:")
    print("输入:", nums, target)
    print("输出:", search_result)
    """
    示例输出结果:
    输入: [4, 5, 6, 7, 0, 1, 2] 0
    输出: 4
    """
